/** 二分查找 （双闭区间）*/
function binarySearch<T>(arr: T[], target: T): number {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    // 防止整数溢出
    const mid = Math.floor(low + (high - low) / 2);
    if (arr[mid] > target) {
      high = mid - 1;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      return mid;
    }
  }
  return -1;
}
// 推荐示例
const arrB = [1, 3, 5, 7, 9];
const target = 5;
console.log(binarySearch(arrB, target)); // 2

/** 二分查找 （左闭右开区间） */
function binarySearch1<T>(arr: T[], target: T): number {
  let low = 0, high = arr.length;
  while (low < high) {
    // 防止整数溢出
    const mid = Math.floor(low + (high - low) / 2);
    if (arr[mid] > target) {
      high = mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      return mid;
    }
  }
  return -1; //未找到元素，返回-1 
}